package april.test_4_9;

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public boolean lemonadeChange(int[] bills) {
        int five = 0;
        int ten = 0;
        for(int i = 0; i < bills.length; i++) {
            if(bills[i] == 5) {
                five++;
            } else if (bills[i] == 10) {
                if (five > 0) {
                    five--;
                    ten++;
                } else {
                    return false;
                }
            } else {
                if (ten > 0 && five > 0) {
                    ten--;
                    five--;
                } else if (five >= 3) {
                    five -= 3;
                } else {
                    return false;
                }
            }
        }
        return true;
    }
    public int halveArray(int[] nums)
    {
        // 创建⼀个⼤根堆
        PriorityQueue<Double> heap = new PriorityQueue<>((a, b) ->
                b.compareTo(a));
        double sum = 0.0;
        // 把元素都丢进堆中，并求出累加和
        for(int x : nums) {
            heap.offer((double)x);
            sum += x;
        }
        sum /= 2.0; // 先算出⽬标和
        int count = 0;
        // 依次取出堆顶元素减半，直到减到之前的⼀半以下
        while(sum > 0) {
            double t = heap.poll() / 2.0;
            sum -= t;
            count++;
            heap.offer(t);
        }
        return count;
    }
    public int maxProfit(int[] prices, int fee) {
        int[] f = new int[prices.length];
        int[] g = new int[prices.length];
        f[0] = -prices[0];
        for (int i = 1; i < prices.length; i++) {
            f[i] = Math.max(f[i - 1],g[i - 1] - prices[i]);
            g[i] = Math.max(g[i - 1], f[i - 1] + prices[i] - fee);
        }
        return g[prices.length - 1];
    }
}
